package 力扣;

/**
 假设按照升序排序的数组在预先未知的某个点上进行了旋转。

 ( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

 编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

 示例 1:

 输入: nums = [2,5,6,0,0,1,2], target = 0
 输出: true
 示例 2:

 输入: nums = [2,5,6,0,0,1,2], target = 3
 输出: false
 */
public class _81搜索旋转排序数组_II {
    // 包含重复数 leetcode 33 题目 唯一的区别就是需要在循环的时候 处理重复数
    public boolean search(int[] nums, int target) {

        int left=0;
        int right=nums.length-1;
        while(left<=right){
            // 处里重复的情况
            while(left<right&&nums[left]==nums[left+1]) ++left;
            while(left<right&&nums[right]==nums[right-1]) --right;
            int mid = (left+right)>>1;
            if( nums[mid] == target ) return true;
            if( nums[mid] >=nums[left] ){ //左边有序
                if( target>= nums[left] && target < nums[mid]){ //判断target是否在有序数组里
                    right = mid - 1;
                }else{
                    left = mid+1;
                }
            }else{ //右边有序
                if( target<= nums[right] && target > nums[mid]){ //判断target是否在有序数组里
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }

        }
        return false;
    }
}
